// // 【2017 年统考真题】
// // 设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。
// // 例如，当下列的两棵表达式树作为算法的输入时：
//     //         *
//     //      /     \
//     //    +         *
//     //   /  \     /  \
//     // a     b   c    -
//     //                  \
//     //                   d
//     //         ↓
//     //         +
//     //       /   \
//     //     *       -
//     //    / \     /  \
//     //   a   b   c    -
//     //               / \
//     //              c   d
//     //输出等价的中缀表达式分别为（a+b）*（c*（-d））和（a*b）+（c-（c-d））。
// // 要求：
// // （1）给出算法的基本设计思想
// // （2）根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释
//
// #include <stdio.h>
// #include <stdlib.h>
// #include"windows.h"
//
// typedef char ElemData;
//
// typedef struct TreeNode {
//     ElemData data;
//     struct TreeNode* left;
//     struct TreeNode* right;
// }TreeNode;
//
// // 创建树节点
// TreeNode* CreateTreeNode(ElemData x) {
//     TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
//     if (newNode == NULL) {
//         perror("CreateTreeNode()::malloc()");
//         exit(1);
//     }
//     newNode->data = x;
//     newNode->left = newNode->right = NULL;
//     return newNode;
// }
//
// // 插入树节点（二叉搜索树规则）
// TreeNode* InsertTreeNode(TreeNode* root, ElemData x) {
//     if (root == NULL) {
//         return CreateTreeNode(x);
//     }
//     if (x < root->data) {
//         root->left = InsertTreeNode(root->left, x);
//     } else {
//         root->right = InsertTreeNode(root->right, x);
//     }
//     return root;
// }
//
// void TreeOther(TreeNode* root,int deep) {
//     if(root==NULL) {//空
//         return;
//     }
//     if(root->left==NULL&&root->right==NULL) {//根节点
//         printf("%c ",root->data);
//     }else {
//         if(deep>1) {
//             printf("%c ",'(');
//         }
//         TreeOther(root->left,deep+1);
//         printf("%c ",root->data);
//         TreeOther(root->right,deep+1);
//         if(deep>1) {
//             printf("%c ",')');
//         }
//     }
// }
//
// void TreeRoot(TreeNode* root,int deep) {//根节点和叶子节点一样,不需要加括号
//     TreeOther(root,1);
// }
//
// // 释放二叉树
// void freeTree(TreeNode* root) {
//     if (root) {
//         freeTree(root->left);
//         freeTree(root->right);
//         free(root);
//     }
// }
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     TreeNode* root = NULL;
//
//     // 构建第一棵表达式树
//     root = CreateTreeNode('*');
//     root->left = CreateTreeNode('+');
//     root->right = CreateTreeNode('*');
//     root->left->left = CreateTreeNode('a');
//     root->left->right = CreateTreeNode('b');
//     root->right->left = CreateTreeNode('c');
//     root->right->right = CreateTreeNode('-');
//     root->right->right->right = CreateTreeNode('d');
//
//     printf("第一棵表达式树的中缀表达式: ");
//     TreeRoot(root,1);
//     printf("\n");
//
//     freeTree(root);
//
//     // 构建第二棵表达式树
//     root = CreateTreeNode('+');
//     root->left = CreateTreeNode('*');
//     root->right = CreateTreeNode('-');
//     root->left->left = CreateTreeNode('a');
//     root->left->right = CreateTreeNode('b');
//     root->right->left = CreateTreeNode('c');
//     root->right->right = CreateTreeNode('-');
//     root->right->right->left = CreateTreeNode('c');
//     root->right->right->right = CreateTreeNode('d');
//
//     printf("第二棵表达式树的中缀表达式: ");
//     TreeRoot(root,1);
//     printf("\n");
//
//     freeTree(root);
//
// }
//
// // 解：
// // （1）基于二叉树的中序遍历方式即可得到该表达式
// // （2）算法实现：将二叉树的中序遍历递归算法稍加变形即可得到。
// // 除根结点而哼叶子结点外，遍历到其他结点是在遍历其左子树之前加上左括号，
// // 遍历完右子树后加上右括号：
//
//
//
//
//
//
//
